package com.arron.algorithm.leetcodetop100.技巧.原地hash;

import java.util.HashSet;
import java.util.Set;

/**
 *  异或法：
 *  @see com.arron.algorithm.leetcodetop100.技巧.异或.丢失的数字
 *  二分查找 ：
 * @see com.arron.algorithm.leetcodetop100.二分查找.丢失的数字
 */
public class 丢失的数字 {



    // 原地hash
    public int missingNumber(int[] nums) {

        int len = nums.length;


        for (int i = 0; i < len; i++) {
            while (nums[i] >= 1 && nums[i] <= len && nums[nums[i]-1] != nums[i]){
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;

            }
        }

        for (int i = 0; i < len; i++) {
            if (nums[i] != i+1){
                return i+1;
            }
        }

        return 0;

    }


    public void swap(int a,int b){
        a ^= b;
        b ^= a;
        a ^= b;
    }

}
